package cn.fxzhang.leetcode.no02;

/**
 * 220. 存在重复元素 III
 * 给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。
 * 如果存在则返回 true，不存在返回 false。
 * 示例 1：
 * 输入：nums = [1,2,3,1], k = 3, t = 0
 * 输出：true
 * 提示：
 * 0 <= nums.length <= 2 * 10^4
 * -2^31 <= nums[i] <= 2^31 - 1
 * 0 <= k <= 10^4
 * 0 <= t <= 2^31 - 1
 * 类型：排序
 * 题解：排序后比较下标和差值是否符合要求
 * 时间复杂度：O(N^2)
 * 空间复杂度：O(N)
 *
 * 提交记录(1/2)： 注意溢出
 * 执行用时: 10 ms, 击败了93.18%
 * 内存消耗: 38.9 MB, 击败了94.77%
 *
 * 【中等】通过次数46,994提交次数171,221
 * @author 张晓帆
 * @date 2021/4/17
 */
public class P0220_Contains_Duplicate_Iii {

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int n = nums.length;
        if (n<2){
            return false;
        }
        int[] idx = new int[n];
        for (int i=0; i<n; i++){
            idx[i] = i;
        }
        quickSort(nums, idx, 0, n-1);
        for (int i=0; i<n-1; i++){
            int j=i+1;
            while(j<n && nums[j]-nums[i]>=0 && nums[j]-nums[i]<=t){
                if (Math.abs(idx[i]-idx[j])<=k){
                    return true;
                }
                j++;
            }
        }
        return false;
    }

    public void quickSort(int[] nums, int[] idx, int l, int r){
        if (l >= r){
            return;
        }
        int p = partition(nums, idx, l, r);
        quickSort(nums, idx, l, p-1);
        quickSort(nums, idx, p+1, r);
    }

    private int partition(int[] nums, int[] idx, int l, int r) {
        //int p = (l+r)>>1;
        //swap(nums, idx, l, p);
        int key = nums[l];
        int j = l+1;
        for (int i=l+1; i<=r; i++){
            if (nums[i]<=key){
                swap(nums, idx, j, i);
                j++;
            }
        }
        swap(nums, idx, l, j-1);
        return j-1;
    }

    private void swap(int[] a, int[] idx, int i, int j){
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
        tmp = idx[i];
        idx[i] = idx[j];
        idx[j] = tmp;
    }
}
